package com.fzy.test.leetcode348;

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Main test = new Main();
    }

    public int minimizedStringLength(String s) {

        Set<Character> set = new HashSet<>();
        for(int i = 0;i<s.length();i++){
            set.add(s.charAt(i));
        }

        return set.size();
    }

    public int semiOrderedPermutation(int[] nums) {
        if(nums[0] == 1 && nums[nums.length-1] == nums.length){
            return 0;
        }
        int n = nums.length;
        int ans = 0;
        int index = 0;
        for(int i = 0;i<n;i++){
            if(nums[i] == 1){
                index = i;
                break;
            }
        }

        for(int i = index;i>=1;i--){
            int val = nums[i];
            nums[i] = nums[i-1];
            nums[i-1] = val;
            ans++;
        }

        int tail = 0;
        for(int i = 0;i<n;i++){
            if(nums[i] == nums.length){
                tail = i;
                break;
            }
        }
        for(int i = tail;i<n-1;i++){
            int val = nums[i];
            nums[i] = nums[i+1];
            nums[i+1] = val;
            ans++;
        }

        return ans;
    }

    public long matrixSumQueries(int n, int[][] queries) {
        int[][] initArr = new int[n][n];

        for(int[] query : queries){
            if(query[0] == 0){
                for(int i = 0;i<n;i++){
                    initArr[query[1]][i] = query[2];
                }
            }else {
                for(int i = 0;i<n;i++){
                    initArr[i][query[1]] = query[2];
                }
            }
        }
        int ans = 0;

        for(int[] arr : initArr){
            ans += Arrays.stream(arr).sum();
        }
        return ans;
    }

    public int count(String num1, String num2, int min_sum, int max_sum) {
        int mod = (int)1e9 + 7;
        int n = num2.length();
        // 定义状态数组
        int[][][] f = new int[n+1][max_sum+1][2];
        // 初始化状态
        for (int j = min_sum; j <= max_sum; j++) {
            f[0][j][0] = 1;
        }
        // 逐位转移
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= max_sum; j++) {
                for (int k = 0; k <= 1; k++) {
                    for (int a = 0; a < 10; a++) {
                        // 上下界均未到达的情况
                        if (k == 0) {
                            if (j-a >= 0) {
                                f[i][j][0] = (f[i][j][0] + f[i-1][j-a][0] + f[i-1][j-a][1]) % mod;
                            }
                        }
                        // 上界已经到达的情况
                        else if (k == 1 && a <= num2.charAt(n-i)-'0') {
                            if (j-a >= 0) {
                                f[i][j][1] = (f[i][j][1] + f[i-1][j-a][0] + f[i-1][j-a][1]) % mod;
                            }
                        }
                        // 下界已经到达的情况
                        else if (a >= num1.charAt(n-i)-'0') {
                            if (j-a >= 0) {
                                f[i][j][1] = (f[i][j][1] + f[i-1][j-a][0] + f[i-1][j-a][2]) % mod;
                            }
                        }
                    }
                }
            }
        }
        // 计算答案
        int ans = 0;
        for (int j = min_sum; j <= max_sum; j++) {
            ans = (ans + f[n][j][1]) % mod;
        }
        return ans;
    }
}
